牛顿二项式定理 发布于 2020-05-10 | 分类于 二项式定理 、 组合数学 | 3分钟 | 478字数 牛顿二项式定理 (0 ≤ |x| < |y| )(x+y)α=∑k=0∞(αk)xkyα−k(x+y)^{\alpha} = \sum_{k=0}^{\infty} \binom{\alpha}{k} {x}^{k} {y}^{\alpha-k} \tag{0 $\leq$ |x| < |y| } (x+y)α=k=0∑∞(kα)xkyα−k(0 ≤ |x| < |y| ) 阅读全文 »
容斥:错位排列 发布于 2020-05-10 | 分类于 容斥 、 组合数学 | 6分钟 | 1130字数 容斥:错位排列 令 {1,2,...,n1,2,...,n1,2,...,n} 的一个错位排列,是一个排列 a1,a2,...,an{a_1,a_2,...,a_n}a1,a2,...,an,使得 a1≠1,a2≠2,...,an≠n{a_1}\ne{1},{a_2}\ne{2},...,{a_n}\ne{n}a1=1,a2=2,...,an=n。 令 DnD_nDn 表示大小为 nnn 的错位排列的方案数。 阅读全文 »
常用组合数公式的证明 发布于 2020-05-07 | 分类于 组合数学 | 8分钟 | 1556字数 常用组合数公式的证明 证明中可能用到的一些前置知识,这里我不再给出他们证明: (1)(x+y)n=∑k=0n(nk)xkyn−k(x+y)^n=\sum_{k=0}^n{\binom{n}{k}{x}^{k}{y}^{n-k}}\tag{1} (x+y)n=k=0∑n(kn)xkyn−k(1) (2)(n+1k+1)=(nk+1)+(nk)\binom{n+1}{k+1}=\binom{n}{k+1}+\binom{n}{k}\tag{2} (k+1n+1)=(k+1n)+(kn)(2) 上述是著名的二项式公式和帕斯卡公式,下面我们将利用他们对另外的一些组合数公式予以证明。 阅读全文 »
偏序集和等价关系 发布于 2020-05-05 | 分类于 偏序集 、 离散数学 、 拓扑排序 | 7分钟 | 1750字数 偏序集和等价关系 不得不说关于离散数学的定义太抽象,而实在难以理解。 阅读全文 »
Ramsey 定理 发布于 2020-05-03 | 分类于 容斥 、 组合数学 | 4分钟 | 841字数 RamseyRamseyRamsey 定理 这一节是关于鸽巢原理的部分拓展,其实用处并不太大吧 阅读全文 »
CSP-S2019游记 发布于 2019-11-17 | 分类于 NOIP 、 游记 | 4分钟 | 1020字数 CSP-S2019 游记 前言 凉兮人愿。本空违,今不见,苍然如沐,已是霜雪千年。 阅读全文 »